# 700.二叉搜索树中的搜索
# 给定二叉搜索树（BST）的根节点root和一个整数值val。
# 你需要在BST中找到节点值等于val的节点。 返回以该节点为根的子树。 如果节点不存在，则返回null 。
#
# 示例1:
# 输入：root = [4, 2, 7, 1, 3], val = 2
# 输出：[2, 1, 3]
#
# 示例2:
# 输入：root = [4, 2, 7, 1, 3], val = 5
# 输出：[]


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def searchBST(self, root:[TreeNode], val: int) ->[TreeNode]:
        # 这个好像直接俄可以用层序遍历写出来,找到值就返回当前值所在节点
        from collections import deque
        que = deque()
        que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                if cur.val == val:
                    return cur
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
        return None

    def searchBST2(self, root: [TreeNode], val: int) -> [TreeNode]: # 递归试试
        def traver(root,val):
            if not root:
                return
            if root.val == val:
                return root
            if root.val > val:
                return traver(root.left,val)
            else:
                return traver(root.right,val)
        return traver(root,val)

    def searchBST3(self, root: [TreeNode], val: int) -> [TreeNode]:  # 迭代
        stack = []
        stack.append(root)
        while stack:
            cur = stack.pop()
            if cur.val == val:
                return cur
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)

if __name__ == '__main__':
    a31 = TreeNode(1)
    a32 = TreeNode(3)
    a21 = TreeNode(2,a31,a32)
    a22 = TreeNode(7)
    a11 = TreeNode(4,a21,a22)
    val = 2
    tmp = Solution()
    # res = tmp.searchBST(a11,val)
    # res = tmp.searchBST2(a11,val)
    res = tmp.searchBST3(a11,val)
    print(res.val)
    print(res.left.val)
    print(res.right.val)
